Digital signal processors are processors specifically designed to handle digital signal processing tasks. Such devices have seen exponential growth over the last decade in consumer products such as cellular phones, automobile radios, voice recognition devices, scientific instrumentation, etc. Digital processors are used in such applications because of the intensive math computations that are required. The execution speed of most DSP algorithms is limited almost completely by the number multiplications and additions required.
In real time processing where digital processors are most useful, an output signal is produced the same time that the input signal is being acquired. In many applications utilizing DSP's, the output information must be immediately available after the input signal is received, although a short delay is permissible. For example, a ten millisecond delay in a telephone call is not detectable by the speaker or listener. Similarly, a few second delay in the radar signal processing before the signal is displayed is negligible. In such real time applications a sample of a signal is received, an algorithm executed, and an output sample transmitted, with this process occurring over and over. Alternatively, a group of samples may be received as a group, processed as a group and then transmitted as a group of samples.
Functions such as filters and mixers in DSP systems require signal samples to be multiplied by precalculated coefficients. In the case of a filter such as a FIR or IIR filter, the coefficients are the typical FIR and IIR coefficients, and in the case of a mixer, they are the set of values representing a mixer injection signal.
In the prior art, multipliers used to implement such filters and mixers are sometimes designed such that for any part of the multiplier where the signal is being multiplied by a zero bit in the coefficient, the multiplication was not actually performed. For example, if the coefficient was 0.5, with the binary representation of 010000000 (for an 8-bit coefficient), only multiplication due to the non-zero bit would be performed. Typically, multiplications carried out for the non-zero bits are sometimes implemented by shift-and-add techniques. As previously indicated, it would be advantageous to reduce the number of non-zero bits to in turn reduce the number of multiplications required. Accordingly, the fewer multiplications required in a DSP algorithm the faster or more efficiently the algorithm will execute.
Alternatively, for a function that is to be executed within a fixed time period, computational resources, such as multipliers, can be shared for use by different parts of the function if those computational resources are made faster by reducing the number of non-zero bits. Thus, the required computational resources to perform the whole function are reduced. An example is a filter, where one multiplier may perform all of the multiplications required to implement the filter. A reduction in required computational resources results in a more efficient and thus lower cost implementation of the function.
Finally, in the implementation of a desired function, a reduction in the number of non-zero bits of any coefficients required to implement the function will result in a reduction in the required digital logic and thus the cost required to implement the function.
Therefore what is needed is a new and improved method for reducing the number of non-zero bits in values, such as filter and mixer coefficients used in multiplication operations in DSP algorithms. Such an algorithm should have a reduced execution time or lower implementation cost while having little to no affect on the quality or usability of the output signal.